{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Set Matrix Zeroes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: setZeroes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵置零"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个&nbsp;<code><em>m</em> x <em>n</em></code> 的矩阵，如果一个元素为 <strong>0 </strong>，则将其所在行和列的所有元素都设为 <strong>0</strong> 。请使用 <strong><a href=\"http://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95\" target=\"_blank\">原地</a></strong> 算法<strong>。</strong></p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/17/mat1.jpg\" style=\"width: 450px; height: 169px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[1,1,1],[1,0,1],[1,1,1]]\n",
    "<strong>输出：</strong>[[1,0,1],[0,0,0],[1,0,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/17/mat2.jpg\" style=\"width: 450px; height: 137px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]\n",
    "<strong>输出：</strong>[[0,0,0,0],[0,4,5,0],[0,3,1,0]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == matrix.length</code></li>\n",
    "\t<li><code>n == matrix[0].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= matrix[i][j] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一个直观的解决方案是使用 &nbsp;<code>O(<em>m</em><em>n</em>)</code>&nbsp;的额外空间，但这并不是一个好的解决方案。</li>\n",
    "\t<li>一个简单的改进方案是使用 <code>O(<em>m</em>&nbsp;+&nbsp;<em>n</em>)</code> 的额外空间，但这仍然不是最好的解决方案。</li>\n",
    "\t<li>你能想出一个仅使用常量空间的解决方案吗？</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [set-matrix-zeroes](https://leetcode.cn/problems/set-matrix-zeroes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [set-matrix-zeroes](https://leetcode.cn/problems/set-matrix-zeroes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1],[1,0,1],[1,1,1]]', '[[0,1,2,0],[3,4,5,2],[1,3,1,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None: \n",
    "        setFirstRowToZero = True if 0 in matrix[0] else False\n",
    "        for iRow in range(1,len(matrix)): \n",
    "            for iCol in range(len(matrix[0])): \n",
    "                if matrix[iRow][iCol] == 0:\n",
    "                    matrix[0][iCol] = 0\n",
    "                    matrix[iRow][0] = 0\n",
    "        for iRow in range(1,len(matrix)): \n",
    "            for iCol in range(1,len(matrix[0])): \n",
    "                if matrix[iRow][0] == 0 or matrix[0][iCol] == 0:\n",
    "                    matrix[iRow][iCol] = 0\n",
    "        if matrix[0][0] == 0:\n",
    "            for iRow in range(len(matrix)):\n",
    "                matrix[iRow][0] = 0\n",
    "        if setFirstRowToZero: matrix[0] = [0] * len(matrix[0])\n",
    "\n",
    "# Test cases: \n",
    "# [[0,1] [1,1]] -> [[0,0],[0,1]]\n",
    "#\n",
    "#\n",
    "#               time        space\n",
    "# Limits:       O(mn)       O(1)\n",
    "# Approach 1:   O(mn)       O(m+n) wcs\n",
    "# Create sets of rows and columns to be set to zero\n",
    "# Then iterate through those, and set them to zero\n",
    "# \n",
    "# Approach 2:   O(nm)       O(1)\n",
    "# Set temporarily to special value \n",
    "# Then loop through and change special values to 0\n",
    "#\n",
    "# Approahc "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: 'List[List[int]]') -> 'None':\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        try:\n",
    "            r, c = len(matrix), len(matrix[0])\n",
    "        except:\n",
    "            pass\n",
    "        row, col = [], []\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if not matrix[i][j]:\n",
    "                    row.append(i)\n",
    "                    col.append(j)\n",
    "        for rnum in row:\n",
    "            for j in range(c):\n",
    "                matrix[rnum][j] = 0\n",
    "        for cnum in col:\n",
    "            for i in range(r):\n",
    "                matrix[i][cnum] = 0\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: 'List[List[int]]') -> 'None':\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        pos = []\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[i])):\n",
    "                if matrix[i][j] == 0:\n",
    "                    pos.append([i, j])\n",
    "        for p in pos:\n",
    "            for i in range(len(matrix)):\n",
    "                matrix[i][p[1]] = 0\n",
    "            for j in range(len(matrix[0])):\n",
    "                matrix[p[0]][j] = 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return\n",
    "        n = len(matrix[0])\n",
    "        col = set()\n",
    "        row = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    col.add(j)\n",
    "                    row.add(i)\n",
    "        for i in range(m):\n",
    "            if i in row:\n",
    "                matrix[i] = [0 for j in range(n)]\n",
    "            for j in range(n):\n",
    "                if j in col:\n",
    "                    matrix[i][j] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        for col in range(m):\n",
    "            for rom in range(n):\n",
    "                if matrix[col][rom]==0:\n",
    "                    #上边和下边\n",
    "                    for top in range(col):\n",
    "                        matrix[top][rom] = 0\n",
    "                    for bottom in range(m-1,col,-1):\n",
    "                        if matrix[bottom][rom]!=0:\n",
    "                            matrix[bottom][rom] = \"*\"\n",
    "                    #右边无零时\n",
    "                    if 0 not in matrix[col][rom+1:]:\n",
    "                        matrix[col] = [0 for _ in range(n)]\n",
    "                        break\n",
    "                    else:\n",
    "                        matrix[col][:rom] = [0 for _ in range(rom)]\n",
    "                if matrix[col][rom]==\"*\":\n",
    "                    matrix[col][rom] = 0\n",
    "        print(matrix)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        firstrow = False\n",
    "        firstcol = False\n",
    "        mr = len(matrix)\n",
    "        mc = len(matrix[0])\n",
    "        for i in range(mr):\n",
    "            if matrix[i][0] == 0:\n",
    "                firstcol = True\n",
    "                break\n",
    "        for i in range(mc):\n",
    "            if matrix[0][i] == 0:\n",
    "                firstrow = True\n",
    "                break\n",
    "        for i in range(mr):\n",
    "            for j in range(mc):\n",
    "                if matrix[i][j] == 0:\n",
    "                    matrix[0][j] = 'i'\n",
    "                    matrix[i][0] = 'i'\n",
    "        print(matrix)\n",
    "        for i in range(1,mr):\n",
    "            if matrix[i][0] == 'i':\n",
    "                matrix[i] = [0] * mc\n",
    "        for i in range(1,mc):\n",
    "            if matrix[0][i] == 'i':\n",
    "                for x in range(mr):\n",
    "                    matrix[x][i] = 0\n",
    "        if firstrow == True:\n",
    "            matrix[0] = [0] * mc\n",
    "        if firstcol == True:\n",
    "            for x in range(mr):\n",
    "                matrix[x][0] = 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        if len(matrix) == 0:\n",
    "            return matrix\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "\n",
    "        is_zero = [[False for _ in range(cols)] for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                is_zero[i][j] = 0 == matrix[i][j]\n",
    "        print(is_zero)\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if matrix[i][j]==0 and is_zero[i][j]:\n",
    "                    for m in range(cols):\n",
    "                        matrix[i][m] = 0\n",
    "                    for n in range(rows):\n",
    "                        matrix[n][j] = 0\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        rows = set()\n",
    "        cols = set()\n",
    "        for i,c in enumerate(matrix):\n",
    "            for j,v in enumerate(c):\n",
    "                if v==0:\n",
    "                    rows.add(i)\n",
    "                    cols.add(j)\n",
    "        for r in rows:\n",
    "            j = 0\n",
    "            while j<n:\n",
    "                matrix[r][j] = 0\n",
    "                j += 1\n",
    "        for c in cols:\n",
    "            i = 0\n",
    "            while i<m:\n",
    "                matrix[i][c] = 0\n",
    "                i += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        index = []\n",
    "\n",
    "        for i in range(len(matrix)):\n",
    "\n",
    "            for j in range(len(matrix[i])):\n",
    "\n",
    "                if matrix[i][j] == 0:\n",
    "\n",
    "                    index.append((i, j))\n",
    "\n",
    "        for i, j in index:\n",
    "\n",
    "            matrix[i] = [0] * len(matrix[i])\n",
    "\n",
    "            for k in range(len(matrix)):\n",
    "\n",
    "                matrix[k][j] = 0\n",
    "\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def add_zero(self,a,b,new):\n",
    "        for i in range(len(new)):\n",
    "            new[i][b]='0'+new[i][b]\n",
    "        for i in range(len(new[0])):\n",
    "            new[a][i]='0'+new[a][i]\n",
    "    def setZeroes(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        new=[[str(matrix[i][j]) for j in range(len(matrix[0]))]for i in range(len(matrix))]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if int(matrix[i][j])==0:\n",
    "                    self.add_zero(i,j,new)\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if new[i][j][0]=='0':\n",
    "                    matrix[i][j]=0\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(matrix); n = len(matrix[0])\n",
    "        target = 0; zeroIndex = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    zeroIndex.append((i,j))\n",
    "        for row, column in zeroIndex:\n",
    "            self.setZ(matrix,row,0,target,n)\n",
    "            self.setZ(matrix,column,1,target,m)\n",
    "\n",
    "        \n",
    "    def setZ(self,matrix, index, axis,target,m):\n",
    "        if axis == 0:\n",
    "            for i in range(m):\n",
    "                matrix[index][i] = target\n",
    "        if axis == 1:\n",
    "            for j in range(m):\n",
    "                matrix[j][index] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: 'List[List[int]]') -> 'None':\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        row = [0]*len(matrix)\n",
    "        cow = [0]*len(matrix[0])\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == 0:\n",
    "                    row[i],cow[j] = 1,1\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if row[i]==1 or cow[j]==1:\n",
    "                    matrix[i][j]=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        r=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]==0:\n",
    "                    r.append([i,j])\n",
    "        for i in r:\n",
    "            matrix[i[0]]=[0 for _ in range(n)]\n",
    "        for i in r:\n",
    "            for j in range(m):\n",
    "                matrix[j][i[1]]=0\n",
    "        return matrix\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        import functools\n",
    "        first_col = functools.reduce(lambda acc, i: acc or matrix[i][0] == 0, range(len(matrix)), False)\n",
    "        first_row = functools.reduce(lambda acc, j: acc or matrix[0][j] == 0, range(len(matrix[0])), False)\n",
    "\n",
    "        for i in range(1, len(matrix)):\n",
    "            for j in range(1, len(matrix[0])):\n",
    "                if matrix[i][j] == 0:\n",
    "                    matrix[i][0], matrix[0][j] = 0, 0\n",
    "\n",
    "        for i in range(1, len(matrix)):\n",
    "            for j in range(1, len(matrix[0])):\n",
    "                if matrix[i][0] == 0 or matrix[0][j] == 0:\n",
    "                    matrix[i][j] = 0\n",
    "\n",
    "        if first_col:\n",
    "            for i in range(len(matrix)):\n",
    "                matrix[i][0] = 0\n",
    "\n",
    "        if first_row:\n",
    "            for j in range(len(matrix[0])):\n",
    "                matrix[0][j] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        m_list = set()\n",
    "        n_list = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    m_list.add(i)\n",
    "                    n_list.add(j)\n",
    "        for i in range(m):\n",
    "            if i in m_list:\n",
    "                matrix[i][:] = [0]*n\n",
    "                continue\n",
    "            for j in n_list:\n",
    "                matrix[i][j] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        setofrow=set()\n",
    "        setofcol=set()\n",
    "        for i,x in enumerate(matrix):\n",
    "            for j,y in enumerate(x):\n",
    "                if y==0:\n",
    "                    setofrow.add(i)\n",
    "                    setofcol.add(j)\n",
    "        for i in setofrow:\n",
    "            for j in range(len(matrix[0])):\n",
    "                matrix[i][j]=0\n",
    "        for j in setofcol:\n",
    "            for i in range(len(matrix)):\n",
    "                matrix[i][j]=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\r\n",
    "        \"\"\"\r\n",
    "        Do not return anything, modify matrix in-place instead.\r\n",
    "        \"\"\"\r\n",
    "        # row, col = len(matrix), len(matrix[0])\r\n",
    "        # zero_row, zero_col = set(), set()\r\n",
    "        # for i in range(row):\r\n",
    "        #     for j in range(col):\r\n",
    "        #         if matrix[i][j] == 0:\r\n",
    "        #             zero_row.add(i)\r\n",
    "        #             zero_col.add(j)\r\n",
    "\r\n",
    "        # for i in range(row):\r\n",
    "        #     for j in range(col):\r\n",
    "        #         if i in zero_row or j in zero_col:\r\n",
    "        #             matrix[i][j] = 0\r\n",
    "\r\n",
    "\r\n",
    "        is_col = False\r\n",
    "        row, col = len(matrix), len(matrix[0])\r\n",
    "        \r\n",
    "        for i in range(row):\r\n",
    "            if matrix[i][0] == 0:\r\n",
    "                is_col = True\r\n",
    "            for j in range(1, col):\r\n",
    "                if matrix[i][j] == 0:\r\n",
    "                    matrix[i][0] = 0\r\n",
    "                    matrix[0][j] = 0\r\n",
    "\r\n",
    "        for i in range(1, row):\r\n",
    "            for j in range(1, col):\r\n",
    "                if matrix[i][0] == 0 or matrix[0][j] == 0:\r\n",
    "                    matrix[i][j] = 0\r\n",
    "\r\n",
    "        if matrix[0][0] == 0:\r\n",
    "            for j in range(1, col):\r\n",
    "                matrix[0][j] = 0\r\n",
    "\r\n",
    "        if is_col:\r\n",
    "            for i in range(row):\r\n",
    "                matrix[i][0] = 0\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        is_col = False\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        for i in range(row):\n",
    "            if matrix[i][0]==0:\n",
    "                is_col = True\n",
    "            \n",
    "            for j in range(1, col):\n",
    "                if matrix[i][j]==0:\n",
    "                    matrix[i][0] = 0\n",
    "                    matrix[0][j] = 0\n",
    "\n",
    "        \n",
    "        for i in range(1, row):\n",
    "            for j in range(1, col):\n",
    "                if matrix[0][j]==0 or matrix[i][0]==0:\n",
    "                    matrix[i][j] = 0\n",
    "        \n",
    "        if matrix[0][0]==0:\n",
    "            for j in range(col):\n",
    "                matrix[0][j] = 0\n",
    "        \n",
    "        if is_col:\n",
    "            for i in range(row):\n",
    "                matrix[i][0]=0\n",
    "\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        zeroPos=[(x,y) for x in range(len(matrix)) for y in range(len(matrix[0])) if matrix[x][y]==0]\n",
    "        xAxis=list(set([x for (x,_) in zeroPos]))\n",
    "        yAxis=list(set([y for (_,y) in zeroPos]))\n",
    "        for x in xAxis:\n",
    "            for y in range(len(matrix[0])):\n",
    "                matrix[x][y]=0\n",
    "        for y in yAxis:\n",
    "            for x in range(len(matrix)):\n",
    "                matrix[x][y]=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    for k in range(m):\n",
    "                        matrix[k][j] = -float('inf') if matrix[k][j] != 0 else 0\n",
    "                    for k in range(n):\n",
    "                        matrix[i][k] = -float('inf') if matrix[i][k] != 0 else 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == -float('inf'):\n",
    "                    matrix[i][j] = 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        ss0,ss1=set(),set()     #存储该改变的行，列\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                print(matrix[i][j])\n",
    "                if matrix[i][j]==0:\n",
    "                    print(i,j)\n",
    "                    ss0.add(i)\n",
    "                    ss1.add(j)\n",
    "        \n",
    "        for x in ss0:\n",
    "            for j in range(n):\n",
    "                matrix[x][j]=0\n",
    "        for x in ss1:\n",
    "            for j in range(m):\n",
    "                matrix[j][x]=0\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        rows,cols = set(), set()\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]==0:\n",
    "                    rows.add(i)\n",
    "                    cols.add(j)\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if i in rows or j in cols:\n",
    "                    matrix[i][j]=0\n",
    "        return \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        colFlag = False\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == 0:\n",
    "                    if j == 0:\n",
    "                        colFlag = True\n",
    "                    else:\n",
    "                        matrix[0][j] = 0\n",
    "                    matrix[i][0] = 0\n",
    "        for i in range(len(matrix)-1, -1, -1):\n",
    "            for j in range(1, len(matrix[0])):\n",
    "                if matrix[i][0] == 0 or matrix[0][j] == 0:\n",
    "                    matrix[i][j] = 0\n",
    "        if colFlag:\n",
    "            for i in range(len(matrix)):\n",
    "                matrix[i][0] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    将矩阵中的元素置为0，这可以原地进行且不占用额外空间\n",
    "    难点在于如何使用常数空间，记录0元素出现的位置：\n",
    "        两个整数，位运算\n",
    "    '''\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        x = y = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    x |= (1 << i)\n",
    "                    y |= (1 << j)\n",
    "\n",
    "        for i in range(x.bit_length()):\n",
    "            if (x >> i) & 1 == 1:\n",
    "                for j in range(n):\n",
    "                    matrix[i][j] = 0\n",
    "        \n",
    "        for j in range(y.bit_length()):\n",
    "            if (y >> j) & 1 == 1:\n",
    "                for i in range(m):\n",
    "                    matrix[i][j] = 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        i = len(matrix)\n",
    "        j = len(matrix[0])\n",
    "        row,col =[False]*i,[False]*j\n",
    "\n",
    "\n",
    "        for a in range(i):\n",
    "            for b  in range(j):\n",
    "                if matrix[a][b] == 0:\n",
    "                    row[a]=col[b]=True\n",
    "\n",
    "        for a in range(i):\n",
    "            for b in range(j):\n",
    "                if row[a] or col[b]:\n",
    "                    matrix[a][b]=0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        row0_flag = any(matrix[0][i] == 0 for i in range(n))\n",
    "        col0_flag = any(matrix[j][0] == 0 for j in range(m))\n",
    "\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    matrix[i][0]=0\n",
    "                    matrix[0][j] = 0\n",
    "\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if matrix[i][0]==0 or matrix[0][j] == 0:\n",
    "                    matrix[i][j] = 0\n",
    "        \n",
    "        if row0_flag:\n",
    "            for j in range(n):\n",
    "                matrix[0][j] = 0\n",
    "\n",
    "        if col0_flag:\n",
    "            for i in range(m):\n",
    "                matrix[i][0] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        row0_flag = False\n",
    "        col0_flag = False\n",
    "        # 找第一行是否有0\n",
    "        for j in range(col):\n",
    "            if matrix[0][j] == 0:\n",
    "                row0_flag = True\n",
    "                break\n",
    "        # 第一列是否有0\n",
    "        for i in range(row):\n",
    "            if matrix[i][0] == 0:\n",
    "                col0_flag = True\n",
    "                break\n",
    "\n",
    "        # 把第一行或者第一列作为 标志位\n",
    "        for i in range(1, row):\n",
    "            for j in range(1, col):\n",
    "                if matrix[i][j] == 0:\n",
    "                    matrix[i][0] = matrix[0][j] = 0\n",
    "        #print(matrix)\n",
    "        # 置0\n",
    "        for i in range(1, row):\n",
    "            for j in range(1, col):\n",
    "                if matrix[i][0] == 0 or matrix[0][j] == 0:\n",
    "                    matrix[i][j] = 0\n",
    "\n",
    "        if row0_flag:\n",
    "            for j in range(col):\n",
    "                matrix[0][j] = 0\n",
    "        if col0_flag:\n",
    "            for i in range(row):\n",
    "                matrix[i][0] = 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        r0 = 0\n",
    "        c0 = 0\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        for i in range(n):\n",
    "            if matrix[0][i]==0:\n",
    "                r0 = 1\n",
    "                break\n",
    "        for i in range(m):\n",
    "            if matrix[i][0]==0:\n",
    "                c0 = 1\n",
    "                break\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    matrix[i][0]=0\n",
    "                    matrix[0][j]=0\n",
    "        for j in range(1,n):\n",
    "            if matrix[0][j]==0:\n",
    "                i = 1\n",
    "                while i<m:\n",
    "                    matrix[i][j]=0\n",
    "                    i+=1\n",
    "        for i in range(1,m):\n",
    "            if matrix[i][0]==0:\n",
    "                j = 1\n",
    "                while j<n:\n",
    "                    matrix[i][j]=0\n",
    "                    j+=1\n",
    "        if r0==1:\n",
    "            for i in range(n):\n",
    "                matrix[0][i]=0\n",
    "        if c0==1:\n",
    "            for i in range(m):\n",
    "                matrix[i][0]=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        row = [False]*len(matrix)\n",
    "        col = [False]*len(matrix[0])\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]==0:\n",
    "                    row[i]=True\n",
    "                    col[j]= True\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if row[i] or col[j]:\n",
    "                    matrix[i][j] = 0\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        def f(i,j):\n",
    "            for x in range(m):\n",
    "                if 0<= x < m  and matrix[x][j]!= 0:\n",
    "                    matrix[x][j] = -inf\n",
    "            for y in range(n):\n",
    "                if 0<= y < n and matrix[i][y]!= 0:\n",
    "                    matrix[i][y] = -inf\n",
    "            return\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    f(i,j)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == -inf:\n",
    "                    matrix[i][j] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        height = len(matrix)\n",
    "        width  = len(matrix[0])\n",
    "        height_record = []\n",
    "        width_record  = []\n",
    "\n",
    "        for i in range(height):\n",
    "            for j in range(width):\n",
    "                if matrix[i][j] == 0:\n",
    "                    height_record.append(i)\n",
    "                    width_record.append(j)\n",
    "        height_record = list(set(height_record))\n",
    "        width_record  = list(set(width_record))\n",
    "        for i in height_record:\n",
    "            for j in range(width):\n",
    "                matrix[i][j] = 0\n",
    "        \n",
    "        for j in width_record:\n",
    "            for i in range(height):\n",
    "                matrix[i][j] = 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        row=[0]*m\n",
    "        col=[0]*n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]==0:\n",
    "                    row[i]=1\n",
    "                    col[j]=1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if row[i]==1 or col[j]==1:\n",
    "                    matrix[i][j]=0\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        row, col = len(matrix) * [False], len(matrix[0]) * [False]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == 0:\n",
    "                    row[i] = True\n",
    "                    col[j] = True\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if row[i] or col[j]:\n",
    "                    matrix[i][j] = 0"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
